package JAVAcollectionsanddatastructures.List;

import java.util.ArrayList;
import java.util.List;

//杨辉三角：可以看作一个直角三角形，每一行第一个和最后一个为1，其他数等于它左右上方两数之和！
public class YangHuitriangle {
  public List<List<Integer>> generate(int numRows){
      List<List<Integer>> ret = new ArrayList<>();//二维数组

      //第一行
      List<Integer> list1 = new ArrayList<>();
      list1.add(1);
      ret.add(list1);

      for (int i = 1; i < numRows; i++) {
          List<Integer> list = new ArrayList<>();//除了第一行，后面的每一行
          list.add(1);//使得每一行的开始都是1

          List<Integer> preRow = ret.get(i-1);//获取前一行
          for (int j = 1; j < i; j++) {
              //每一行中间的情况
              int num1 = preRow.get(j) + preRow.get(j-1);//每个数等于它左右上方两数之和
              list.add(num1);
          }
          list.add(1);//每一行最后都为1
          ret.add(list);//将每一行放到二维数组中
      }
      return ret;
  }
}
